An internet communications network 80 is depicted in FIG. 1 including five transit or backbone networks A, B, C, D, and E and three stub networks R, Y, and Z. A "backbone" network is an intermediary network which conveys communicated data from one network to another network. A "stub" network is a terminal or endpoint network from which communicated data may only initially originate or ultimately be received. Each network, such as the stub network R, includes one or more interconnected subnetworks such as I, J, L and M. As used herein, the term "subnetwork" refers to a collection of one or more nodes, e.g., (d), (a) (b, x, y), (q, v) (r, z), (s, u), (e, f, g), (h, i), (j, k, 1), (m, n), and (o, p), interconnected by wires and switches for local internodal communication. Each subnetwork may be a local area network or LAN. Each subnetwork has one or more interconnected nodes which may be host computers ("hosts") u, v, w, x, y, z (shown as triangles in FIG. 1) or routers a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s (shown as squares in FIG. 1). A host is an endpoint node from which communicated data may initially originate or ultimately be received. A router is a node which serves solely as an intermediary node between two other nodes; the router receives communicated data from one node and retransmits the data to another node.
FIG. 2 shows a block diagram of a host or router node 10. As shown, the node may include a CPU 11, a memory 12 and one or more I/O ports 13-1, 13-2, . . . , 13-N connected to a bus 14. Illustratively, each I/O port 13-1, 13-2, . . . , 13-N is connected by wires, optical fibers, and/or switches to the I/O port of another node. The I/O ports 13-1, 13-2, . . . , 13-N are for transmitting communicated data in the form of a bitstream organized into one or more packets to another node and for receiving a packet from another node. An exemplary packet 40 is shown in FIG. 3 having a payload 41 which contains communicated data and one or more headers 42 which contain control and/or address information.
A host which initially generates a packet for transmission to another node is called the source node and a host which ultimately receives the packet is called a destination node. Communication may be achieved between a single source node and a single destination node using a process called unicast routing. In unicast routing, packets are transferred via a sequence of nodes including the source node, zero or more intermediary nodes, and the destination node, in a bucket brigade fashion. For example, a packet may be communicated from the node w to the node x by transferring the packet from the node w to the node c, to the node d, to the node b, and to the node x. The particular sequence of nodes via which a packet is transmitted is also referred to as a "path". In the above example, one path from the source node w to the destination node x includes the nodes (w,c,d,b, and x).
When a source node transmits a packet to a single destination node, the source node writes the destination address of the packet in a destination address field 43 (FIG. 3) of the header 42. Illustratively, each node of the internet 80 is assigned a unique internet address which is used for identifying the node for purposes of transmitting a packet thereto. The source node then retrieves an entry from a forwarding table, such as the entry 51 of the table 50 shown in FIG. 4, which entry is indexed by the destination address of the packet. (Illustratively, the particular forwarding table 50 shown in FIG. 4 is stored at the node a.) The forwarding table stores a number of entries which entries each contains information for routing a received packet to its ultimate destination. Each indexed entry of the forwarding table indicates the next node on the path to the destination node (where the address of the destination node is used as the index to retrieve the entry). For example, at the node a, the entry 51 indicates that the next node on the path to the node y is the node b. The source node then transmits the packet to the next node on the path indicated by the retrieved entry. This process is repeated at each intermediary node until the packet arrives at the destination node.
Sometimes a source node has a packet to transmit to more than one destination node. For example, the packet may contain an electronic mail or E-mail letter to be delivered to each user of a particular mail group which users are each located at different destination nodes. Alternatively, the packet may contain voice data of a speaking teleconference participant at a source node to be simultaneously delivered to a number of listening teleconference participants located at different destination nodes. Such packets may be transmitted from the source node to each destination node according to a routing procedure depicted in FIG. 5.
FIG. 5 depicts a portion 75 of an internet. As shown in FIG. 5, a packet to be transmitted to a particular group of destination nodes d1, d2, d3, d4, d5, and d6 is transmitted from a source s1 to a first router r1. Illustratively, the router r1 connects the stub containing the source node s1 to the internet 75. The router r1 transmits the packet to the node r2. At the node r2, the packet is transmitted to the destination node d6 via the router r3. In addition, the router r2 transmits a copy of the packet to the router r4. The router r4 receives the copy of the packet and transmits a copy of the received packet to the destination node d1 via the nodes r5 and r6. In addition, the router r4 transmits a copy of the received packet to the router r7. The router r7, transmits a copy of the received packet to the destination node d2 via the router r8. The router r7 transmits a copy of the received packet to the destination node d3 via the routers r9 and r10. In addition, the router r7 transmits a copy of the received packet to the router r11. The router r11 receives the packet and transmits a copy of the received packet to the destination node d4 via the router r12 and a copy of the received packet to the destination node d5 via the router r13.
The packet delivery process shown in FIG. 5 is referred to as multicast routing. In multicast routing, as a packet propagates from router to router, the packet is selectively replicated at certain routers so that sufficient copies of the packet are generated and transmitted to each destination node of a multicast group. Collectively, the paths shown in FIG. 5, i.e., the sequences of nodes which interconnect all of the nodes of a particular group form a tree called a multicast tree. A path of the multicast tree between any two nodes, e.g., the path from the node r2 to the node r11 including the nodes (r2, r4, r7, and r11) is referred to as a branch. There is only one branch on the multicast tree between any two nodes.
There are several conventional methods for implementing multicast routing, in particular, for constructing and maintaining multicast trees. See S. Deering, "Multicast Routing in Internetworks and Extended LANs," ACM Symposium on Communication Architectures and Protocols, ACM SIGCOMM, pp. 55-64, Aug., 1988. Conventionally, multicast tree construction is sender based. That is, for each multicast group, one multicast tree is constructed between each potential source node, i.e., each node that can potentially transmit multicast packets, and the corresponding destination nodes which receive packets from the source node. Appropriate routing information for each pair of a multicast group and a source node is stored at each router on each multicast tree.
In multicast tree construction, the Internet Group Management Protocol ("IGMP") may be utilized for purposes of determining which host nodes in each subnetwork desire to join which multicast groups. According to IGMP, a router node is designated as an interrogator for a subnetwork. The interrogator transmits a query packet over the associated subnetwork to each host. The hosts which receive this query packet respond by indicating of which multicast groups the hosts are members. The interrogator subsequently performs steps according to a multicast tree construction method for attaching itself to each appropriate multicast tree depending on which multicast groups were indicated by the responding host nodes of the subnetwork.
Most nodes are able to distinguish between unicast and multicast packets based on their addresses. In the Internet Protocol ("IP"), the address space is partitioned into unicast addresses and multicast addresses. Each multicast group is assigned one of the multicast addresses. A source node desiring to transmit a packet writes the multicast address of the multicast group and the unicast address of the source node in the packet header. When a node receives a packet with a multicast address, the receiving node utilizes the unicast source address of the source node and the multicast address of the multicast group contained in the packet header to retrieve the set of nodes to which the packet must be transmitted.
One conventional multicast tree construction method is provided in a multicast routing method called Distance-Vector Multicast Routing Protocol ("DVMRP"). This multicast tree construction method uses a modified reverse path forwarding algorithm to construct shortest path, sender-based multicast trees. A multicast tree is constructed according to DVMRP as follows. Initially, a source node transmits the first few multicast packets without using a multicast tree. Instead, the source node transmits the multicast packets in a manner such that a copy of each multicast packet is transmitted via each backbone network. For example, each router which receives one of the first few multicast packets transmits a copy of the packet to each other router attached thereto. Routers which receive these packets may indicate that they are not on a path to a destination node of the multicast group by transmitting a packet containing a special "prune" message to the router from which the multicast packet was received. A particular router may transmit a prune message if:
For each source node-multicast group pair, each router keeps track of from which routers prune messages have been received. When a router subsequently receives packets transmitted from the same source node to the same multicast group, the router retransmits copies of the packet to only those routers which did not transmit a prune message in previous multicast communications between this source node and multicast group.
Another conventional multicast tree construction method is provided in a multicast routing method called the Link-State Multicast Routing Protocol. According to this multicast tree construction method, each router maintains information regarding each link or each direct connection to another node. In addition, for each link, each router maintains a list of each multicast group having one or more member nodes on that link, i.e., having one or more member nodes connected to the router via that link. Each router disseminates these lists for each multicast group to the other routers of the internet. Furthermore, whenever a new multicast group is added to, or an old multicast group is deleted from a link, (or the nodes interconnected via particular link changes) a designated router on that link transmits a message packet to each other router in the internet indicating the change. Because each router possesses full knowledge of which members of each group are on each link, any router receiving a multicast packet can compute an optimal multicast tree to all routers possessing links with member nodes of the multicast group of the packet. For example, if a router receives a packet from a host, the router will selectively transmit copies of the packet to other routers. Each router which receives a copy of the packet performs a consistent calculation for determining to which routers copies of the packet must be retransmitted therefrom. Invariably, the copies of the packets are received at routers having links with member nodes of the multicast group of the packet. The copies of the packet are then transmitted via the appropriate links to the member nodes.
The conventional methods for constructing multicast trees are disadvantageous in that each utilizes a vast amount of storage space. This is because the conventional methods construct multicast trees which are source node based, i.e., a distinct multicast tree is constructed from each potential source node to the rest of the destination nodes of each multicast group. If there are N groups and S potential source nodes for each multicast group then the storage space requirement at each node is on the order of S.times.N. In addition, the above-mentioned conventional methods have certain specific disadvantages. In DVMRP, all routers must participate in constructing a multicast tree, even if they do not wish to be part of any multicast tree. Furthermore, the routers in DVMRP utilize a vast amount of processing resources in constructing a tree initially or modifying a tree in the event the internet is reconfigured. Likewise, in Link-State Multicast Routing, each router consumes a large amount of processing resources whenever a designated router transmits a packet to each other router of the internet which packet indicates a change in the internet or group membership. Moreover, in Link-State Multicast Routing, each router must store membership information over the entire internet.
It is an object of the present invention to overcome the disadvantages of the prior art.